#include "common.h"
#include "cpfs.h"
//
#include "cxutil/popcount.h"

// global constant

static size_t const CpfsPathMax = 4096;

using std::min;
using std::max;
using boost::format;
using std::string;

namespace cpfs {

static unsigned long ffz(unsigned long const word)
{
#ifdef _MSC_VER
    long unsigned index = -1;
#else
    int off = -1;
#endif
    assert(~word != 0);
#ifdef _MSC_VER
    verify(_BitScanForward(&index, ~word));
    assert(0 <= index && index < sizeof(word) * CHAR_BIT);
    return index;
#else
    off = __builtin_ctzl(~word);
    assert(0 <= off && (size_t)off < sizeof(word) * CHAR_BIT);
    return off;
#endif
}

#ifndef BITS_PER_LONG
#   define BITS_PER_LONG sizeof(long) * CHAR_BIT
#endif

/*
 * Find the first cleared bit in a memory region.
 */
static unsigned long find_first_zero_bit(
    const unsigned long *addr,
    unsigned long size)
{
    const unsigned long *p = addr;
    unsigned long result = 0;
    unsigned long tmp;

    while (size & ~(BITS_PER_LONG-1)) {
        if (~(tmp = *(p++)))
            goto found;
        result += BITS_PER_LONG;
        size -= BITS_PER_LONG;
    }
    if (!size)
        return result;

    tmp = (*p) | (~0UL << size);
    if (tmp == ~0UL)    /* Are any bits zero? */
        return result + size;   /* Nope. */
found:
    return result + ffz(tmp);
}

struct Handle {
    Ino ino;
    Handle() : ino(-1) {}
};

struct Geo {
    size_t block_size;
    Blkno total_length;
    Blkno indirect_density;
    Blkno bitmap_density;
    Blkno master_start;
    Blkno master_length;
    Blkno master_end;
    Blkno bitmap_start;
    Blkno bitmap_length;
    Blkno bitmap_end;
    Blkno data_start;
    Blkno data_length;
    Blkno data_end;
    size_t inode_inline_data_length;
};
class PathCache : public std::map<std::string, Ino> {};
class BlockCache : public std::map<Blkno, void *> {};

typedef std::vector<Handle> HandleTable;

struct Cpfs {
    // internal file handle table
    HandleTable htab;
    // a binary tree of blocks used to handle the current request
    BlockCache block_cache;
    //__gnu_cxx::hash_map<cpfs::Blkno, void *> block_cache;
    PathCache path_cache;
    // index of last bitmap block an allocation occurred
    Blkno bmblki;
    // free block count, updated on first statvfs
    Blkno freeblks;
    // filesystem parameters set when loaded
    CpfsParams params;
    // this might be a pointer to RO zero page via mmap
    //void const *zeroed;
    // geometry of filesystem, calculated when loaded
    Geo geo;
    Device device;

    Cpfs(char const *path, CpfsOff size, CpfsOff off);
    ~Cpfs();
    bool valid() const;

    void block_read(Blkno blkno, void *buf) const {
        device.read_block(blkno, buf, geo.block_size);
    }
    void block_write(Blkno blkno, void const *buf) {
        device.write_block(blkno, buf, geo.block_size);
    }
};
bool Cpfs::valid() const {
    return 0 <= bmblki && bmblki < geo.bitmap_length
        // anywhere from not yet read, to not even a root inode
        && -1 <= freeblks && freeblks <= geo.data_length;
}
static void cpfs_load_geometry(
        struct Bootrec const *const br,
        struct Geo *const geo) {
    memset(geo, -1, sizeof(*geo));
    geo->block_size = br->blksize;
    Blkno blocks_left = geo->total_length = br->blkcount;
    geo->indirect_density = geo->block_size / sizeof(Blkno);
    geo->bitmap_density = br->blksize * CHAR_BIT;
    geo->master_start = 0;
    geo->master_length = 1;
    blocks_left -= geo->master_length;
    geo->master_end = geo->master_start + geo->master_length;
    geo->bitmap_start = geo->master_end;
    // 1 bitmap blocks to every bitmap_density data blocks rounded UP
    geo->bitmap_length =
        ((int_least64_t)blocks_left + geo->bitmap_density)
        / (geo->bitmap_density + 1);
    blocks_left -= geo->bitmap_length;
    geo->bitmap_end = geo->bitmap_start + geo->bitmap_length;
    geo->data_start = geo->bitmap_end;
    geo->data_length = blocks_left;
    geo->data_end = geo->data_start + geo->data_length;
    geo->inode_inline_data_length =
        (geo->block_size - offsetof(struct Inode, inline_data))
        / sizeof(*((struct Inode *)NULL)->inline_data);
    LOGF(Info, boost::format("Inodes contain %u inlined data blocks.") %
        geo->inode_inline_data_length);

    assert(geo->bitmap_start);
    assert(geo->bitmap_length * geo->bitmap_density >= geo->data_length);
    assert(geo->data_start);
}
Cpfs::Cpfs(
        char const *const path,
        CpfsOff const size,
        CpfsOff const off)
:   htab(20),
    bmblki(0),
    freeblks(-1),
    device(path, size, off)
{
    struct Bootrec *br = static_cast<decltype(br)>(alloca(512));
    device.read(br, 512, 0);
    if (0 != strncmp("cpfs1", br->fsident, COUNTOF(br->fsident))) {
        throw std::runtime_error(str(boost::format(
            "Unrecognized filesystem identifier %.32s") % br->fsident));
    }
    cpfs_load_geometry(br, &geo);
    params.devpath = strdup(path);
    params.namemax = CPFS_NAME_MAX;
    params.serial = br->serial;
}
Cpfs::~Cpfs() {
#ifndef NDEBUG
    void *const buf = alloca(geo.block_size);
#endif
    for (auto it(block_cache.begin()); it != block_cache.end(); ++it) {
    #ifndef NDEBUG
        block_read(it->first, buf);
        assert(0 == memcmp(it->second, buf, geo.block_size));
    #endif
        free(it->second);
    }
    free(params.devpath);
}
class CallContext
{
private:
    Blkno free_bitmap_block_index_;
    Blkno free_block_count_;
    PathCache const &path_cache_;
    PathCache path_changes_;
    BlockCache &clean_blocks_;
    BlockCache dirty_blocks_;
    std::set<Blkno> freed_blknos_;
    CpfsTime optime_;
    Geo const &geo_;
    Device const &device_;
    HandleTable handle_table_;

public:
    CallContext(Cpfs &cpfs)
    :   free_bitmap_block_index_(cpfs.bmblki),
        free_block_count_(cpfs.freeblks),
        path_cache_(cpfs.path_cache),
        clean_blocks_(cpfs.block_cache),
        optime_(-1),
        geo_(cpfs.geo),
        device_(cpfs.device),
        handle_table_(cpfs.htab)
    {
        cpfs_errno_clear();

        assert(cpfs.valid());

        //cpfs().device.flush();

        //assert(cpfs().block_cache.empty());
        //assert(!cpfs().block_cache.has_dirty_blocks());
    }
    ~CallContext()
    {
        for (auto it(dirty_blocks_.begin()); it != dirty_blocks_.end(); ++it) {
            free(it->second);
        }
    }
    void commit(Cpfs &cpfs) {
        cpfs.bmblki = free_bitmap_block_index_;
        cpfs.freeblks = free_block_count_;
        for (   auto it(freed_blknos_.begin());
                it != freed_blknos_.end();
                ++it) {
            // the changes should be reverted when the block was freed
            assert(!dirty_blocks_.count(*it));
            LOGF(Debug, "Removing blkno %|| from the block cache", *it);
            auto clean(cpfs.block_cache.find(*it));
            if (clean != cpfs.block_cache.end()) {
                free(clean->second);
                cpfs.block_cache.erase(clean);
            }
        }
        // write all pending block changes
        {
            size_t block_write_count = 0;
            for (   auto dirty(dirty_blocks_.begin());
                    dirty != dirty_blocks_.end();
                    ++dirty) {
                assert(!freed_blknos_.count(dirty->first));
                auto clean(cpfs.block_cache.find(dirty->first));
                if (    clean == cpfs.block_cache.end()
                        || 0 != memcmp(
                            clean->second,
                            dirty->second,
                            cpfs.geo.block_size)) {
                    cpfs.block_write(dirty->first, dirty->second);
                    block_write_count += 1;
                }
                if (clean == cpfs.block_cache.end()) {
                    verify(cpfs.block_cache.insert(*dirty).second);
                    dirty->second = nullptr;
                } else {
                    std::swap(clean->second, dirty->second);
                }
            }
            //cpfs().device.flush();
            LOGF(Debug, "Synced dirty cache (%|| dirty, %|| written).",
                dirty_blocks_.size(), block_write_count);
        }
        for (   auto dirty(path_changes_.begin());
                dirty != path_changes_.end();
                ++dirty) {
            if (dirty->second == -1) {
                cpfs.path_cache.erase(dirty->first);
            } else {
                assert(0 == freed_blknos_.count(dirty->second));
                cpfs.path_cache[dirty->first] = dirty->second;
            }
        }
        cpfs.htab = handle_table_;
    }
    CpfsTime const &optime() {
        if (optime_ == -1) {
            struct timespec ts;
            if (0 != clock_gettime(CLOCK_REALTIME, &ts)) abort();
            optime_ = timespec_to_cpfstime(&ts);
        }
        if (optime_ == -1) abort();
        return optime_;
    }

    Geo const &geo() const {
        return geo_;
    }
    void block_read(Blkno blkno, void *buf) const {
        device_.read_block(blkno, buf, geo().block_size);
    }
    bool valid_ino(Ino const ino) const {
        return
            geo().data_start <= ino && ino < geo().data_end
            && ino != -1;
    }
    bool fd_valid(CpfsFd const fd) const {
        return valid_ino(handle_table_.at(fd).ino);
    }
    CpfsFd handle_open(Ino const ino) {
        BOOST_FOREACH(Handle &handle, handle_table_) {
            if (handle.ino == -1) {
                handle.ino = ino;
                return &handle - &handle_table_.front();
            }
        }
        throw CpfsError(TooManyOpenFiles);
    }
    Handle const &handle_get(CpfsFd const fd) {
        if (!fd_valid(fd)) throw CpfsError(BadFileDescriptor);
        return handle_table_.at(fd);
    }
    void handle_close(CpfsFd const fd) {
        if (!fd_valid(fd)) throw CpfsError(BadFileDescriptor);
        Handle &handle(handle_table_.at(fd));
        Inode &inode(*inode_get(handle.ino));
        handle.ino = -1;
        if (inode_is_dir(inode) && !ino_is_open(inode.ino)) {
            dir_repack(inode);
        }
        inode_sweep(inode);
    }
    Ino root_ino() const {
        return geo().data_start;
    }
    static bool root_reset(
            char const *const path,
            CpfsOff size,
            CpfsOff off) {
        LOGF(Info, "Creating root inode");
        Cpfs *cpfs = (cpfs::Cpfs *)cpfs_load(path, size, off);
        if (!cpfs) return false;
        CallContext call(*cpfs);
        // root inode starts with 777 perms mainly to ease debugging during dev
        // this can be changed as necessary to a more suitable value
        Inode *const inode = call.inode_init(
            CPFS_ITYP_DIR, (CpfsPerms){perms: 0777}, geteuid(), getegid());
        if (!inode) return false;
        assert(inode->ino == call.root_ino());
        // creation of adam
        inode->nlink += 1;
        call.commit(*cpfs);
        return true;
    }
    Inode *create_inode(
            char const *const path,
            CpfsInodeType const type,
            CpfsPerms const perms,
            CpfsUid const uid,
            CpfsGid const gid)
    {
        char dir[CpfsPathMax];
        char const *base;
        if (!(base = path_split(path, dir)))
            return NULL;
        if (!strcmp(dir, "/") && !strlen(base)) {
            cpfs_errno_set(IsRoot);
            return NULL;
        }
        // check parent exists and get its inode
        struct Inode *parent_inode = path_inode(dir);
        if (!parent_inode)
            return NULL;
        // check the name isn't already present
        assert(!cpfs_errno_isset());
        if (dir_has_name(dir, *parent_inode, base)) {
            cpfs_errno_set(FileExists);
            return NULL;
        }
        else if (cpfs_errno_isset())
            return NULL;
        struct Inode *const inode = inode_init(type, perms, uid, gid);
        if (!inode)
            return NULL;
        dir_add_entry(dir, *parent_inode, base, *inode);
        return inode;
    }
    // -1 is error
    Blkno bitmap_avail_raw() {
        Blkno avail = geo_.bitmap_length * geo_.bitmap_density;
        LOGF(Debug, "Total bitmap region bits == %||", avail);
        void *const buf = alloca(geo_.block_size);
        for (   Blkno blkno = geo_.bitmap_start;
                blkno != geo_.bitmap_end;
                ++blkno) {
            void const *p(block_get_ro(blkno, false));
            if (!p) {
                p = buf;
                block_read(blkno, buf);
            }
            avail -= popcount_buffer(p, geo_.block_size);
        }
        LOGF(Debug, "Available blocks == %||", avail);
        return avail;
    }

    Blkno bitmap_avail()
    {
        if (free_block_count_ == -1) {
            free_block_count_ = bitmap_avail_raw();
        }
        return free_block_count_;
    }

    struct BitmapIndex {
        Blkno blkno;
        size_t byte;
        size_t bit;
    };

    bool bitmap_index_valid(BitmapIndex const &bi) const {
        return geo().bitmap_start <= bi.blkno
            && bi.blkno < geo().bitmap_end
            && bi.byte < geo().block_size
            && bi.bit < CHAR_BIT;
    }

    BitmapIndex bitmap_locate(Blkno const blkno)
    {
        assert(data_blkno_valid(blkno));
        BitmapIndex bmidx;
        Blkno const bmbitidx = blkno - geo().data_start;
        assert(bmbitidx >= 0); // why would we free the root inode?
        bmidx.blkno = geo().bitmap_start + (bmbitidx / geo().bitmap_density);
        Blkno const blkbitoff = bmbitidx % geo().bitmap_density;
        bmidx.byte = NUMERIC_CAST(size_t, blkbitoff / CHAR_BIT);
        bmidx.bit = blkbitoff % CHAR_BIT;
        assert(bitmap_index_valid(bmidx));
        return bmidx;
    }

    void bitmap_unset(Blkno const blkno)
    {
        BitmapIndex bmidx = bitmap_locate(blkno);
        char unsigned *block =
            VOID_CAST(decltype(block), block_get(bmidx.blkno, false));
        assert(block[bmidx.byte] & (1 << bmidx.bit));
        block[bmidx.byte] &= ~(1U << bmidx.bit);
        if (free_block_count_ != -1) ++free_block_count_;
        LOGF(Debug, "Released block %"PRIdBLKNO, blkno);
    }

    void bitmap_set(Blkno const blkno)
    {
        BitmapIndex bmidx = bitmap_locate(blkno);
        char unsigned *block =
            VOID_CAST(decltype(block), block_get(bmidx.blkno, false));
        assert(!(block[bmidx.byte] & (1 << bmidx.bit)));
        block[bmidx.byte] |= 1 << bmidx.bit;
        if (free_block_count_ != -1) --free_block_count_;
        LOGF(Debug, "Allocated block %"PRIdBLKNO, blkno);
    }

    bool bitmap_isset(Blkno const blkno)
    {
        BitmapIndex bmidx = bitmap_locate(blkno);
        char unsigned const *block =
            VOID_CAST(decltype(block), block_get_ro(bmidx.blkno));
        return block[bmidx.byte] & (1 << bmidx.bit);
    }

    bool block_alloc(Blkno &blkno)
    {
        for (Blkno i = free_bitmap_block_index_; ;)
        {
            void const *data = NULL;
            long bit = -1;
            assert(0 <= i && i < geo().bitmap_length);
            data = block_get_ro(i + geo().bitmap_start);
            if (!data)
                return false;
            bit = find_first_zero_bit(VOID_CAST(const long unsigned *, data), NUMERIC_CAST(size_t, geo().bitmap_density));
            if (bit < geo().bitmap_density) {
                blkno = geo().data_start + i * geo().bitmap_density + bit;
                bitmap_set(blkno);
                unfreed_blkno(blkno);
                LOGF(Debug, "Allocated block %"PRIdBLKNO".", blkno);
                free_bitmap_block_index_ = i;
                return true;
            } else {
                assert(bit == geo().bitmap_density);
                i = (i + 1) % geo().bitmap_length;
                if (i == free_bitmap_block_index_) {
                    cpfs_errno_set(FilesystemFull);
                    return false;
                }
            }
        }
    }

    // WARNING: block data is zeroed immediately
    FUNCATTR_MUST_CHECK
    bool block_free(Blkno const blkno)
    {
        LOGF(Debug, "Freeing block %lld.", blkno);
        bitmap_unset(blkno);
        // don't check retval coz it might not even be there
        auto it(dirty_blocks_.find(blkno));
        if (it != dirty_blocks_.end()) {
            free(it->second);
            dirty_blocks_.erase(it);
        }
        freed_blkno(blkno);
        return true;
    }

    void block_put(Blkno blkno, void const *src, size_t size)
    {
        assert(size == geo().block_size);
        void *dest = block_get(blkno, true);
        memcpy(dest, src, size);
    }

    void *block_get(Blkno const blkno, bool const clobber)
    {
        assert(blkno_valid(blkno));
        if (data_blkno_valid(blkno))
            assert(bitmap_isset(blkno));
        auto dirty(dirty_blocks_.find(blkno));
        if (dirty != dirty_blocks_.end()) {
            assert(dirty->second);
            return dirty->second;
        }
        auto insret(dirty_blocks_.insert(
            std::make_pair(blkno, malloc(geo().block_size))));
        assert(insret.second);
        dirty = insret.first;
        if (clobber) {
            assert(dirty->second);
            return dirty->second;
        }
        auto clean(clean_blocks_.find(blkno));
        if (clean == clean_blocks_.end()) {
            insret = clean_blocks_.insert(
                std::make_pair(blkno, malloc(geo().block_size)));
            assert(insret.second);
            clean = insret.first;
            block_read(blkno, clean->second);
            //memcpy(dirty->second, clean->second, geo().block_size);
        }
        //memcpy(dirty->second, clean->second, geo().block_size);
        // the clean pointer may already be in use
        std::swap(clean->second, dirty->second);
        memcpy(clean->second, dirty->second, geo().block_size);
        assert(dirty->second);
        return dirty->second;
    }

    void const *block_get_ro(Blkno const blkno, bool cache = true)
    {
        assert(blkno_valid(blkno));
        if (data_blkno_valid(blkno))
            assert(bitmap_isset(blkno));
        auto it(dirty_blocks_.find(blkno));
        if (it != dirty_blocks_.end())
            return it->second;
        it = clean_blocks_.find(blkno);
        if (it != clean_blocks_.end())
            return it->second;
        if (cache) {
            auto insret(clean_blocks_.insert(std::make_pair(
                blkno, malloc(geo().block_size))));
            assert(insret.second);
            block_read(blkno, insret.first->second);
            assert(insret.first->second);
            return insret.first->second;
        } else {
            return nullptr;
        }
    }

    FUNCATTR_MUST_CHECK
     Offset data_capacity(
            Depth depth)
    {
        assert(depth >= 0);
        if (depth <= 0)
            return 0;
        else
        {
            Offset cap = geo().block_size;
            int i;
            for (i = depth; i > 1; --i)
                cap *= geo().indirect_density;
            assert(cap > 0);
            return cap;
        }
    }

    bool data_valid(struct Data const *const data)
    {
        if (data->depth < 0)
            return false;
        else if (data->depth == 0)
        {
            if (data->root != -1)
                return false;
        }
        else
        {
            if (!data_blkno_valid(data->root))
                return false;
            if (data->size <= data_capacity(data->depth - 1))
                return false;
        }
        if (data->size < 0)
            return false;
        return true;
    }

    FUNCATTR_MUST_CHECK
    bool data_truncate_recurse(
            Blkno const blkno,
            int const depth,
            Offset const len)
    {
        assert(data_blkno_valid(blkno));
        if (depth > 1)
        {
            Offset const itemcap = data_capacity(depth - 1);
            Blkno *const indirect = VOID_CAST(Blkno *, block_get(blkno, false));
            size_t itemidx;
            if (!indirect)
                return false;
            for (itemidx = 0; itemidx < geo().indirect_density; ++itemidx)
            {
                Offset const itemlen = len - itemidx * itemcap;
                Blkno const itemblkno = indirect[itemidx];
                if (itemblkno == -1)
                    continue;
                if (!data_truncate_recurse(itemblkno, depth - 1, itemlen))
                    return false;
                if (itemlen <= 0)
                    indirect[itemidx] = -1;
            }
        }
        else
            assert(depth == 1);
        if (len <= 0) {
            if (!block_free(blkno))
                return false;
        }
        return true;
    }

    FUNCATTR_MUST_CHECK
    bool data_truncate_inline(
            Blkno *__restrict inlbnrs,
            size_t inlbcnt,
            Offset const len)
    {
        size_t const &blksize(geo().block_size);

        assert(inlbnrs);
        assert(inlbcnt > 0);
        assert(0 <= len && len < inlbcnt * blksize);
        {
            // round up
            size_t const startidx = boost::numeric_cast<decltype(startidx)>(
                (len / blksize) + !!(len % blksize));
            inlbnrs += startidx;
            inlbcnt -= startidx;
        }
        while (inlbcnt > 0) {
            if (*inlbnrs != -1) {
                if (!block_free(*inlbnrs))
                    return false;
                *inlbnrs = -1;
            }
            inlbnrs += 1;
            inlbcnt -= 1;
        }
        return true;
    }

    bool data_truncate(
            struct Data *const data,
            Blkno *const inlbnrs,
            size_t const inlbcnt,
            Offset const len_)
    {
        Offset len = len_;

        assert(data_valid(data));
        assert(len_ >= 0);

        {
            Offset const inlcap = inlbcnt * geo().block_size;
            if (len < inlcap)
            {
                if (!data_truncate_inline(inlbnrs, inlbcnt, MIN(len, inlcap)))
                    return false;
                len = 0;
            }
            else
            {
                len -= inlcap;
            }
        }
        if (data->root != -1)
        {
            if (!data_truncate_recurse(data->root, data->depth, len))
                return false;
            if (len == 0) {
                assert(!bitmap_isset(data->root));
                data->root = -1;
            }
        }
        while (data->depth && len <= data_capacity(data->depth - 1))
        {
            if (data->root != -1) {
                size_t itemidx;
                Blkno const *indirect = VOID_CAST(
                    decltype(indirect), block_get_ro(data->root));
                assert(data_blkno_valid(indirect[0]));
                for (itemidx = 1; itemidx < geo().indirect_density; ++itemidx)
                    assert(indirect[itemidx] == -1);
                Blkno const newroot = indirect[0];
                if (!block_free(data->root))
                    return false;
                data->root = newroot;
            }
            data->depth -= 1;
        }
        data->size = len_;
        assert(data_valid(data));
        return true;
    }

    FUNCATTR_MUST_CHECK
    ssize_t data_write_recurse(
            Blkno const blkno,
            Depth const depth,
            char const *const buf,
            Offset const count,
            Offset const offset)
    {
        Offset const endoff = offset + count;
    #ifndef NDEBUG
        Offset const datacap = data_capacity(depth);
    #endif
        assert(data_blkno_valid(blkno));
        assert(depth >= 1);
        assert(buf);
        assert(0 < count && count <= datacap);
        assert(0 <= offset && offset < datacap);
        assert(0 < endoff && endoff <= datacap);
        if (depth == 1) {
            assert(datacap == geo().block_size);
            char *block = VOID_CAST(
                decltype(block), block_get(blkno, count == geo().block_size));
            memcpy(block + offset, buf, NUMERIC_CAST(size_t, count));
            return NUMERIC_CAST(ssize_t, count);
        } else {
            ssize_t retcount = 0;
            Blkno *const indirect = VOID_CAST(decltype(indirect), block_get(blkno, false));
            Offset const itemcap = data_capacity(depth - 1);
            for (size_t itemidx = NUMERIC_CAST(size_t, offset / itemcap); ; ++itemidx) {
                Offset const itembase = itemidx * itemcap;
                Offset const bufoff = MAX(itembase - offset, Offset(0));
                Offset const itemoff = MAX(offset - itembase, Offset(0));
                Offset const itemcnt = MIN(
                        endoff - (itembase + itemoff),
                        itemcap - itemoff);
                if (itemcnt > 0)
                {
                    Blkno &itemblkno = indirect[itemidx];
                    assert(itemidx < geo().indirect_density);
                    if (itemblkno == -1) {
                        if (!block_alloc(itemblkno))
                            return -1;
                        if (depth > 2) {
                            void *const data = block_get(itemblkno, true);
                            memset(data, -1, geo().block_size);
                        }
                    }
                    ssize_t writeret = data_write_recurse(
                        itemblkno, depth - 1, buf + bufoff, itemcnt, itemoff);
                    if (writeret == -1)
                        return -1;
                    retcount += writeret;
                }
                else
                    break;
            }
            return retcount;
        }
    }

    FUNCATTR_MUST_CHECK
    bool data_write_inline(
            Blkno *__restrict blknos,
            char const *buf,
            Offset count,
            Offset offset)
    {
        size_t const &blksize = geo().block_size;
        size_t const startidx = NUMERIC_CAST(size_t, offset / blksize);

        assert(blknos);
        assert(buf);
        assert(0 < count);
        assert(0 <= offset);

        blknos += startidx;
        offset -= startidx * blksize;

        while (count != 0) {
            size_t const thiscnt = MIN(count, blksize - offset);
            if (*blknos == -1) {
                if (!block_alloc(*blknos))
                    return false;
            }
            // TODO can this clobber sometimes?
            char *__restrict const data = VOID_CAST(
                decltype(data), block_get(*blknos, false));
            memcpy(data + offset, buf, NUMERIC_CAST(size_t, thiscnt));
            blknos += 1;
            buf += thiscnt;
            count -= thiscnt;
            offset = 0;
        }

        return true;
    }

    ssize_t data_write(
            struct Data *const data,
            Blkno *const inlbnos,
            size_t const inllen,
            char const *buf,
            size_t const &count_,
            Offset const offset_)
    {
        Offset count = count_;
        Offset offset = offset_;

        assert(data_valid(data));
        assert(buf);
        assert(count_ > 0);
        assert(offset_ >= 0);

        {
            Offset const inlcap = inllen * geo().block_size;
            if (offset < inlcap)
            {
                Offset const inlcnt = MIN(count, inlcap - offset);
                if (!data_write_inline(inlbnos, buf, inlcnt, offset))
                    goto fail;
                count -= inlcnt;
                if (count == 0)
                    goto win;
                buf += inlcnt;
                offset = 0;
            }
            else
            {
                offset -= inlcap;
            }
        }

        // deepen until the entire write will fit
        {
            Offset capacity;
            for (   capacity = data_capacity(data->depth);
                    offset + count > capacity;
                    capacity = data_capacity(data->depth))
            {
                Blkno blkno;
                if (!block_alloc(blkno))
                    goto fail;
                // install a rheem
                Blkno *indirect = VOID_CAST(
                    decltype(indirect), block_get(blkno, true));
                memset(indirect, -1, geo().block_size);
                indirect[0] = data->root;
                data->root = blkno;
                data->depth += 1;
            }
        }
        {
            ssize_t const writeret = data_write_recurse(
                    data->root, data->depth, buf, count, offset);
            if (writeret == -1)
                goto fail;
            assert(writeret == count);
        }

    win:
        data->size = max<decltype(data->size)>(offset_ + count_, data->size);
        assert(data_valid(data));
        return count_;
    fail:
        return -1;
    }

    FUNCATTR_MUST_CHECK
    ssize_t data_read_recurse(
            Blkno const blkno,
            int const depth,
            Offset const size,
            char *const buf,
            Offset const count,
            Offset const offset)
    {
        Offset const endoff = offset + count;
    #ifndef NDEBUG
            Offset const cap = data_capacity(depth);
    #endif
        assert(data_blkno_valid(blkno));
        assert(depth >= 1);
        assert(size > 0);
        assert(0 < count && count <= cap);
        assert(0 <= offset && offset < cap);
        assert(0 < endoff && endoff <= cap);

        if (depth == 1)
        {
            assert(cap == geo().block_size);
            {
                char const *block = void_cast(decltype(block), block_get_ro(blkno));
                Offset const readend = MIN(endoff, size);
                ssize_t toread = NUMERIC_CAST(ssize_t, readend - offset);
                memcpy(buf, block + offset, toread);
                return toread;
            }
        }
        else
        {
            ssize_t readcount = 0;
            Blkno const *const indirect = VOID_CAST(
                decltype(indirect), block_get_ro(blkno));
            Offset const itemcap = data_capacity(depth - 1);
            for (size_t itemidx = NUMERIC_CAST(size_t, offset / itemcap); ; ++itemidx) {
                Offset const itembase = itemidx * itemcap;
                Offset const itemoff = MAX(offset - itembase, Offset(0));
                Offset const itemsize = size - itembase;
                Offset const bufoff = MAX(itembase - offset, Offset(0));
                ssize_t const itemcnt = NUMERIC_CAST(decltype(itemcnt), MIN(
                    endoff - (itembase + itemoff),
                    itemcap - itemoff));
                if (itemsize <= 0)
                    assert( itemidx == geo().indirect_density
                            || indirect[itemidx] == -1);
                if (itemcnt > 0 && itemsize > 0)
                {
                    assert(itemidx < geo().indirect_density);
                    if (indirect[itemidx] != -1)
                    {
                        ssize_t readret = data_read_recurse(
                                indirect[itemidx],
                                depth - 1,
                                itemsize,
                                buf + bufoff,
                                itemcnt,
                                itemoff);
                        if (readret == -1)
                            return -1;
                        readcount += readret;
                    }
                    else
                    {
                        memset(buf + bufoff, 0, itemcnt);
                        readcount += itemcnt;
                    }
                }
                else
                    break;
            }
            assert(readcount <= count);
            return readcount;
        }
    }

    FUNCATTR_MUST_CHECK
    bool data_read_inline(
        Blkno const *__restrict blknos,
        char *__restrict buf,
        size_t count,
        Offset offset)
    {
        size_t const blksize = geo().block_size;
        LOGF(Debug, "count=%"PRIdOFFSET" offset=%"PRIdOFFSET, count, offset);
        assert(blknos);
        assert(buf);
        assert(0 < count);
        assert(0 <= offset);
        /* advance the blknos pointer and adjust offset appropriately */
        size_t const startidx = NUMERIC_CAST(size_t, offset / blksize);
        blknos += startidx;
        offset -= startidx * blksize;
        while (count != 0) {
            ssize_t const thiscnt = NUMERIC_CAST(size_t, min<decltype(offset)>(count, blksize - offset));
            if (*blknos != -1) {
                char const *__restrict const data = VOID_CAST(
                    decltype(data), block_get_ro(*blknos));
                if (!data)
                    return false;
                memcpy(buf, data + offset, thiscnt);
            } else {
                memset(buf, 0, thiscnt);
            }
            buf += thiscnt;
            count -= thiscnt;
            offset = 0;
            blknos += 1;
        }
        return true;
    }

    ssize_t data_read(
            struct Data const *const data,
            Blkno const *const inlbnos,
            size_t const inllen,
            char *buf,
            size_t const &count_,
            Offset const offset_)
    {
        assert(data_valid(data));
        assert(buf);
        assert(count_ > 0);
        assert(offset_ >= 0);
        // winret will always be >= 0
        size_t const winret = NUMERIC_CAST(size_t, max<Offset>(
            0,
            min<Offset>(
                count_,
                data->size - offset_)));
        if (winret == 0)
            return 0;
        size_t count = NUMERIC_CAST(decltype(count), winret);
        Offset offset = offset_;
        Offset const inlcap = inllen * geo().block_size;
        if (offset < inlcap) {
            size_t const thiscnt = NUMERIC_CAST(decltype(thiscnt),
                min<Offset>(count, inlcap - offset));
            if (!data_read_inline(inlbnos, buf, thiscnt, offset))
                return -1;
            count -= thiscnt;
            if (count == 0)
                return winret;
            buf += thiscnt;
            offset = 0;
        } else {
            offset -= inlcap;
        }
        Offset const treecap = data_capacity(data->depth);
        if (offset < treecap) {
            size_t const subcount = NUMERIC_CAST(size_t, min<Offset>(count, treecap - offset));
            ssize_t readret = data_read_recurse(
                    data->root, data->depth, data->size, buf, subcount, offset);
            if (readret == -1)
                return -1;
            assert(NUMERIC_CAST(decltype(subcount), readret) == subcount);
            buf += subcount;
            offset = 0;
            count -= subcount;
        } else {
            offset -= treecap;
        }
        if (count > 0) {
            memset(buf, 0, count);
        }

        return winret;
    }
    void dir_add_entry(
            char const *const dirpath,
            Inode &dir,
            char const *const name,
            Inode &inode)
    {
        Dirent de;
        de.ino = inode.ino;
        de.type = inode.type;
        strncpy(de.name, name, CPFS_NAME_MAX);
        if (dir_has_name(dirpath, dir, name)) throw CpfsErrno(FileExists);
        dir_append(dir, de);
        // increment the parent for .. in child dir
        if (inode_is_dir(inode)) dir.nlink += 1;
        dir.ctime = optime();
        dir.mtime = optime();
        inode.nlink += 1;
    }
    void dir_repack(Inode &dir) {
        Dirent de;
        for (   Offset off(0);
                dir_read(nullptr, dir, off, de);
                ++off) {
            if (valid_dirent(de, nullptr)) continue;
            while (true) {
                Offset last = dir_size(dir) - 1;
                if (last <= off) {
                    dir_pop(dir);
                    return;
                }
                verify(dir_read(nullptr, dir, last, de));
                if (valid_dirent(de, nullptr)) {
                    verify(dir_write(dir, de, off));
                    dir_pop(dir);
                    break;
                } else {
                    dir_pop(dir);
                }
            }
            assert(valid_dirent(de, nullptr));
        }
    }
    void dir_remove_entry(
            char const *const dirpath,
            Inode &dir,
            Offset const off,
            Inode *&inode,
            char const *const path) {
        Dirent dirent;
        if (    !dir_read(dirpath, dir, off, dirent)
                || !valid_dirent(dirent, inode)) {
            throw CpfsError(FilesystemCorrupt);
        }
        if (ino_is_open(dir.ino)) {
            dir_write(dir, Dirent(), off);
        } else {
            if (off != dir_size(dir) - 1) {
                dir_read(dirpath, dir, dir_size(dir) - 1, dirent);
                dir_write(dir, dirent, off);
            }
            dir_pop(dir);
        }
        path_cache_remove(path, inode->ino);
        dir.ctime = optime();
        dir.mtime = optime();
        // before the inode is potentially destroyed
        if (inode_is_dir(*inode)) dir.nlink -= 1;
        inode_remove(path, *inode);
    }
    bool dir_find(
            char const *const dirpath,
            Inode const &dir,
            char const *const name,
            Dirent &dirent,
            Offset &off) {
        off = 0;
        for (; dir_read(dirpath, dir, off, dirent); ++off) {
            if (0 == strncmp(name, dirent.name, CPFS_NAME_MAX)) return true;
        }
        return false;
    }
    Ino dir_name_ino(
            char const *const path,
            Inode const &dir,
            char const *const name) {
        Dirent dirent;
        Offset off;
        if (dir_find(path, dir, name, dirent, off)) {
            assert(!strncmp(dirent.name, name, CPFS_NAME_MAX));
            return dirent.ino;
        } else {
            throw CpfsError(PathNotFound);
        }
    }

    bool dir_has_name(
        char const *const dirpath,
        Inode const &dir,
        char const *const name)
    {
        try {
            verify(-1 != dir_name_ino(dirpath, dir, name));
            return true;
        } catch (CpfsError const &exc) {
            if (exc.fserrno == PathNotFound) return false;
            else throw;
        }
    }
    void dir_pop(Inode &dir) {
        assert(dir_size(dir) > 0);
        inode_truncate(&dir, (dir_size(dir) - 1) * sizeof(Dirent));
    }
    Offset dir_size(Inode const &dir) {
        Offset ret(inode_size(dir));
        if (ret % sizeof(Dirent)) throw CpfsError(FilesystemCorrupt);
        ret /= sizeof(Dirent);
        return ret;
    }
    bool dir_write(Inode &dir, Dirent const &dirent, Offset const off) {
        ssize_t writeret = inode_write(&dir, &dirent, sizeof(dirent), sizeof(dirent) * off);
        if (writeret == sizeof(dirent)) return true;
        else if (writeret != -1) throw CpfsError(FilesystemFull);
        else return false;
    }
    bool dir_append(Inode &dir, Dirent const &de) {
        return dir_write(dir, de, dir_size(dir));
    }
    bool valid_dir(Inode const &dir) {
        return valid_inode(dir) && inode_is_dir(dir);
    }
    /** Returns false at end of directory */
    bool dir_read(
        char const *const dirpath,
        Inode const &dir,
        Offset const offset,
        Dirent &dirent)
    {
        switch (inode_read(
                &dir, &dirent, sizeof(dirent), sizeof(dirent) * offset)) {
        case -1:
            throw CpfsError(cpfs_errno_get());
        case 0:
            return false;
        case sizeof(dirent):
            if (valid_dirent(dirent, nullptr) && dirpath) {
                char path[CpfsPathMax];
                path_copy(path, dirpath);
                path_concat(path, dirent.name);
                path_cache_add(path, dirent.ino, true);
            }
            return true;
        default:
            throw CpfsError(FilesystemCorrupt);
        }
    }

    Ino inode_alloc()
    {
        Blkno blkno;
        if (!block_alloc(blkno))
            return -1;
        assert(valid_ino(blkno));
        LOGF(Debug, "ino=%"PRIdINO, blkno);
        return blkno;
    }

    struct Inode const *inode_get_ro(Ino const ino)
    {
        assert(valid_ino(ino));
        struct Inode const *inode = VOID_CAST(decltype(inode), block_get_ro(ino));
        if (!inode)
            return nullptr;
        if (inode->ino != ino || !valid_inode(*inode)) {
            cpfs_errno_set(FilesystemCorrupt);
            return nullptr;
        }
        return inode;
    }

    struct Inode *inode_get(Ino const ino)
    {
        assert(valid_ino(ino));
        struct Inode *inode = VOID_CAST(decltype(inode), block_get(ino, false));
        if (!inode)
            return nullptr;
        if (inode->ino != ino || !valid_inode(*inode)) {
            cpfs_errno_set(FilesystemCorrupt);
            return nullptr;
        }
        return inode;
    }
    Inode *inode_init(
            CpfsInodeType const type,
            CpfsPerms const perms,
            CpfsUid const uid,
            CpfsGid const gid) {
        Ino const ino = inode_alloc();
        struct Inode *inode = NULL;
        if (ino == -1)
            return false;
        inode = static_cast<Inode *>(block_get(ino, true));
        if (!inode)
            return false;
        assert(sizeof(*inode) <= geo().block_size);
        memset(inode, 0, geo().block_size);
        inode->ino = ino;
        inode->type = type;
        inode->perms = perms;
        inode->nlink = (type == CPFS_ITYP_DIR) ? 1 : 0;
        inode->uid = uid;
        inode->gid = gid;
        inode->rdev = 0;
        inode->atime = optime();
        inode->mtime = optime();
        inode->ctime = optime();
        inode->data = DATA_INIT;
        for (size_t a = 0; a < geo().inode_inline_data_length; ++a)
            inode->inline_data[a] = -1;
        assert(valid_inode(*inode));
        return inode;
    }

    CpfsSizeRet inode_read(
            struct Inode const *inode,
            void *buf,
            size_t const &count,
            Offset offset)
    {
        LOGF(Debug, "ino=%||, count=%||, offset=%||", inode->ino, count, offset);
        return data_read(
            &inode->data, inode->inline_data, geo().inode_inline_data_length,
            void_cast(char *, buf), count, offset);
    }
    Offset inode_size(Inode const &inode) {
        return inode.data.size;
    }
    CpfsSizeRet inode_write(
            struct Inode *inode,
            void const *buf,
            size_t const &count,
            Offset offset)
    {
        return data_write(
            &inode->data,
            inode->inline_data,
            geo().inode_inline_data_length,
            void_cast(char const *, buf),
            count,
            offset);
    }
    bool ino_is_open(Ino const ino) {
        BOOST_FOREACH(Handle const &handle, handle_table_) {
            if (handle.ino == ino) {
                return true;
            }
        }
        return false;
    }
    /** Reclaim all resources held by an inode when its no longer in the filesystem or in use. Return true if the inode is removed successfully or still in use. */
    void inode_sweep(Inode &inode) {
        assert(valid_inode(inode));
        /* check that the inode has no references in the filesystem */
        if (inode_is_dir(inode)) {
            if (inode.nlink != 1) return;
            assert(dir_size(inode) == 0);
        } else if (inode.nlink != 0) {
            return;
        }
        if (ino_is_open(inode.ino)) {
            LOGF(Info, boost::format(
                "Inode %|| is still open, delaying removal")
                % (Ino)inode.ino);
            return;
        }
        /* remove the inode's data, and the inode */
        if (!inode_truncate(&inode, 0)) throw CpfsError(cpfs_errno_get());
        if (!block_free(inode.ino)) throw CpfsError(cpfs_errno_get());
        // the inode cannot be used anymore
    }
    void inode_remove(char const *const path, Inode &inode) {
        inode.ctime = optime();
        inode.nlink -= 1;
        if (inode_is_dir(inode) && dir_size(inode)) {
            throw CpfsError(DirectoryNotEmpty);
        }
        inode_sweep(inode);
    }
    bool valid_name(char const *const name) {
        return name[0] && !strchr(name, '/') && strlen(name) <= CPFS_NAME_MAX;
    }
    bool valid_inode(Inode const &inode) {
        if (!valid_ino(inode.ino))
            return false;
        switch (inode.type)
        {
        case CPFS_ITYP_DIR:
            if (inode.nlink < 1)
                return false;
            break;
        case CPFS_ITYP_REG:
        case CPFS_ITYP_FIFO:
        case CPFS_ITYP_LNK:
            if (inode.nlink < 0)
                return false;
            break;
        default:
            return false;
        }
        if (inode.uid == (CpfsUid)-1)
            return false;
        if (inode.gid == (CpfsGid)-1)
            return false;
        if (!data_valid(&inode.data))
            return false;
        {
            size_t i;
            for (i = 0; i < geo().inode_inline_data_length; ++i)
                if (inode.inline_data[i] != -1
                        && !data_blkno_valid(inode.inline_data[i]))
                    return false;
        }
        return true;
    }

    bool inode_truncate(
            struct Inode *inode,
            Offset len)
    {
        return data_truncate(&inode->data, inode->inline_data, geo().inode_inline_data_length, len);
    }

    bool inode_is_dir(Inode const &inode) {
        assert(valid_inode(inode));
        return inode.type == CPFS_ITYP_DIR;
    }
    /** Remove the given path from the cache. Check that the cached ino matches the one given. Return true if the path was removed, and false if it wasn't there to begin with. */
    bool path_cache_remove(
            char const *path,
            Ino const ino VARATTR_UNUSED) {
        auto dirty = path_changes_.find(path);
        if (dirty == path_changes_.end()) {
            auto clean = path_cache_.find(path);
            if (clean == path_cache_.end()) {
                return false;
            } else {
                verify(path_changes_.insert(std::make_pair(path, ino)).second);
                return true;
            }
        } else {
            assert(dirty->second == ino);
            dirty->second = -1;
            return true;
        }
    }
    void path_cache_add(
            char const *path,
            Ino const ino,
            bool const clobber VARATTR_UNUSED) {
        assert(valid_path(path));
        assert(valid_ino(ino));
        // TODO should this be a verify?
        if (!clobber) assert(-1 == path_cache_find(path));
        path_changes_.insert(std::make_pair(path, ino));
    }
    Ino path_cache_find(char const *path) {
        // TODO
    #if 1
        auto dirty = path_changes_.find(path);
        if (dirty == path_changes_.end()) {
            auto clean = path_cache_.find(path);
            if (clean == path_cache_.end()) {
                return -1;
            } else {
                return clean->second;
            }
        }
        return dirty->second;
    #else
        return -1;
    #endif
    }
    bool valid_path(char const *const path) {
        if (    path[0] != '/'
                || (path[1] && path[strlen(path)-1] == '/')
                || strstr(path, "//")) {
            cpfs_errno_set(InvalidPath);
            return false;
        }
        if (strlen(path) >= CpfsPathMax) {
            cpfs_errno_set(PathTooLong);
            return false;
        }
        return true;
    }

    void path_copy(
            char dest[CpfsPathMax],
            char const *path)
    {
        assert(valid_path(path));
        strcpy(dest, path);
    }

    // TODO tighten
    void path_concat(
            char path[CpfsPathMax],
            char const *base)
    {
        assert(valid_path(path));
        assert(strlen(path) + 1 + strnlen(base, CPFS_NAME_MAX) < CpfsPathMax);
        if (path[1]) strcat(path, "/");
        strncat(path, base, CPFS_NAME_MAX);
        assert(valid_path(path));
    }

    char const *path_split(
            char const *const full,
            char dir[CpfsPathMax])
    {
        assert(valid_path(full));

        char const *const sep = strrchr(full, '/');
        char const *const base = sep + 1;
        if (strlen(base) > CPFS_NAME_MAX) throw CpfsError(FilenameTooLong);
        // not the root sep
        if (sep - full) {
            strncpy(dir, full, sep - full);
            dir[sep - full] = '\0';
        } else {
            strcpy(dir, "/");
        }
        LOGF(Debug, "path \"%s\" split into dir \"%s\", name=\"%s\"",
                full, dir, base);
        return base;
    }

    /**
    Finds the longest cached prefix of path and returns its ino, and points to the remaining path.
    */
    char const *path_ino_bootstrap(
            char const *const path,
            char best[CpfsPathMax],
            Ino &ino) {
        assert(valid_path(path));
        strcpy(best, path);
        while (best[0]) {
            ino = path_cache_find(best);
            if (ino != -1) {
                LOGF(Debug, "Bootstrapped ino %"PRIdINO" from \"%s\"", ino, best);
                return path + strlen(best);
            } else {
                char *sep = strrchr(best, '/');
                *sep = '\0';
            }
        }
        assert(!strlen(best));
        strcpy(best, "/");
        ino = root_ino();
        return path;
    }
    Ino path_ino(char const *const path) {
        if (!valid_path(path)) throw CpfsError(InvalidPath);
        Ino ino = -1;
        char sofar[CpfsPathMax], rest[CpfsPathMax];
        strcpy(rest, path_ino_bootstrap(path, sofar, ino));
        assert(valid_ino(ino));
        char *saveptr, *token = strtok_r(rest, "/", &saveptr);
        while (true) {
            if (token == NULL) return ino;
            if (strlen(token) > CPFS_NAME_MAX) throw CpfsError(FilenameTooLong);
            Inode const *const inode = inode_get_ro(ino);
            if (!inode_is_dir(*inode)) throw CpfsError(NotDirectory);
            ino = dir_name_ino(sofar, *inode, token);
            path_concat(sofar, token);
            token = strtok_r(NULL, "/", &saveptr);
        }
    }

    Inode *path_inode(char const *const path)
    {
        return inode_get(path_ino(path));
    }
    Inode const *path_inode_ro(char const *const path) {
        return inode_get_ro(path_ino(path));
    }
    bool blkno_valid(Blkno const blkno)
    {
        return geo().master_end <= blkno && blkno < geo().total_length;
    }

    bool data_blkno_valid(
            Blkno const blkno)
    {
        return geo().data_start <= blkno && blkno < geo().data_end;
    }
    bool valid_dirent(Dirent const &dirent, Inode const *const inode) {
        if (    !valid_ino(dirent.ino)
                || !dirent.name[0]
                || !dirent.type) {
            return false;
        }
        if (inode) {
            assert(valid_inode(*inode));
            if (    dirent.ino != inode->ino
                    || inode->type != dirent.type) {
                return false;
            }
        }
        return true;
    }
    void freed_blkno(Blkno const &blkno)
    {
        verify(freed_blknos_.insert(blkno).second);
    }

    void unfreed_blkno(Blkno const &blkno)
    {
        verify(freed_blknos_.erase(blkno) <= 1);
    }

    void file_truncate(Inode *const inode, Offset const len) {
        assert(valid_inode(*inode));
        assert(len >= 0);
        if (inode_is_dir(*inode)) throw CpfsError(IsDirectory);
        if (inode->data.size == len) return;
        if (!inode_truncate(inode, len)) throw CpfsError(cpfs_errno_get());
        // todo: update ctime, mtime, clear SUID and SGID
        inode->ctime = optime();
        inode->mtime = optime();
    }

    bool call_statvfs(CpfsStatvfs *stfs)
    {
        memset(stfs, 0, sizeof(*stfs));
        stfs->bsize = geo().block_size;
        stfs->namemax = CPFS_NAME_MAX;
        stfs->blocks = geo().data_length;
        stfs->bfree = bitmap_avail();
        return true;
    }

    //TODO rename this to inode_cpfsstat
    void inode_stat(
            struct Inode const *const inode,
            struct CpfsStat *const statbuf)
    {
        assert(valid_inode(*inode));
        //TODO("set st_blocks in struct stat")
        memset(statbuf, -1, sizeof(*statbuf));
        statbuf->ino = inode->ino;
        statbuf->type = static_cast<CpfsInodeType>(inode->type);
        statbuf->perms = inode->perms;
        statbuf->nlink = inode->nlink;
        statbuf->uid = inode->uid;
        statbuf->gid = inode->gid;
        statbuf->rdev = inode->rdev;
        statbuf->size = inode->data.size;
        statbuf->blksize = geo().block_size;
        statbuf->atime = inode->atime;
        statbuf->mtime = inode->mtime;
        statbuf->ctime = inode->ctime;
    }

public:

    bool call_stat(char const *const path, CpfsStat *const st) {
        inode_stat(path_inode_ro(path), st);
        return true;
    }
    bool call_fstat(
            CpfsFd const fd,
            CpfsStat *const statbuf) {
        inode_stat(inode_get_ro(handle_get(fd).ino), statbuf);
        return true;
    }
    CpfsFd call_opendir(char const *const path) {
        Inode const *const inode(inode_get_ro(path_ino(path)));
        if (!inode_is_dir(*inode)) throw CpfsError(NotDirectory);
        return handle_open(inode->ino);
    }
    CpfsFd call_open(char const *const path) {
        return handle_open(path_ino(path));
    }
    bool call_fnop(CpfsFd const fd) {
        if (!fd_valid(fd)) throw CpfsError(BadFileDescriptor);
        return true;
    }
    bool call_close(CpfsFd const fd) {
        handle_close(fd);
        return true;
    }
    bool call_releasedir(CpfsFd const fd) {
        handle_close(fd);
        return true;
    }
    bool call_readdir(
            CpfsFd const fd,
            CpfsOff &off,
            char *const name,
            CpfsStat &st,
            bool const fullstat) {
        Ino const ino(handle_get(fd).ino);
        switch (off) {
        case 0: // start of directory
            off = -2;
            strcpy(name, ".");
            st.ino = ino;
            break;
        case -2: // 2nd item in directory
            off = -1;
            strcpy(name, "..");
            st.ino = -1;
            return true;
        case -1:
            off = 0; // fallthrough
        default: // 3rd item or later
            Inode const *const dir = inode_get_ro(ino);
            Dirent dirent;
            while (true) {
                if (dir_read(NULL, *dir, off, dirent)) {
                    off += 1;
                    if (!valid_dirent(dirent, nullptr)) continue;
                    st.ino = dirent.ino;
                    strncpy(name, dirent.name, CPFS_NAME_MAX);
                    st.type = static_cast<CpfsInodeType>(dirent.type);
                    break;
                } else {
                    off = 0;
                    return true;
                }
            }
        }
        if (fullstat) {
            Inode const *const inode = inode_get_ro(st.ino);
            inode_stat(inode, &st);
        }
        return true;
    }
    bool call_mknod(
            char const *path,
            CpfsInodeType type,
            CpfsPerms perms,
            CpfsUid uid,
            CpfsGid gid) {
        *create_inode(path, type, perms, uid, gid);
        return true;
    }
    CpfsFd call_create(
            char const *const path,
            CpfsInodeType const type,
            CpfsPerms const perms,
            CpfsUid const uid,
            CpfsGid const gid) {
        /* open file if it already exists */
        try {
            return path_ino(path);
        } catch (CpfsError const &exc) {
            if (exc.fserrno != PathNotFound) throw;
        }
        /* create the file if it doesn't */
        return handle_open(create_inode(path, type, perms, uid, gid)->ino);
    }
    bool call_utimens(
            char const *path,
            CpfsTime const tv[2])
    {
        bool retval = false;
        struct Inode *inode = path_inode(path);
        if (inode) {
            inode->atime = tv[0];
            inode->mtime = tv[1];
            retval = true;
        }
        return retval;
    }
    CpfsSizeRet call_read(
            CpfsFd const fd,
            void *const buf,
            size_t const count,
            CpfsOff const off) {
        return inode_read(inode_get(handle_get(fd).ino), buf, count, off);
    }
    CpfsSizeRet call_write(
            CpfsFd const fd,
            void const *const buf,
            size_t const count,
            CpfsOff const off) {
        return inode_write(inode_get(handle_get(fd).ino), buf, count, off);
    }
    bool call_truncate(
            char const *const path,
            CpfsOff const len) {
        file_truncate(path_inode(path), len);
        return true;
    }
    bool call_ftruncate(
            CpfsFd const fd,
            CpfsOff const len) {
        file_truncate(inode_get(handle_get(fd).ino), len);
        return true;
    }
    bool call_rmdir(char const *const path)
    {
        char dirpath[CpfsPathMax] = {'\0'};
        char const *const name = path_split(path, dirpath);
        Inode *const parent = path_inode(dirpath);
        Dirent dirent;
        Offset deoff;
        if (!dir_find(dirpath, *parent, name, dirent, deoff)) {
            throw CpfsError(PathNotFound);
        }
        if (dirent.type != CPFS_ITYP_DIR) throw CpfsError(NotDirectory);
        Inode *inode = inode_get(dirent.ino);
        dir_remove_entry(dirpath, *parent, deoff, inode, path);
        return true;
    }
    bool call_unlink(char const *const path) {
        char dirpath[CpfsPathMax] = {'\0'};
        char const *const name = path_split(path, dirpath);
        Inode *const parent = path_inode(dirpath);
        Dirent dirent;
        Offset deoff;
        if (!dir_find(dirpath, *parent, name, dirent, deoff)) {
            throw CpfsError(PathNotFound);
        }
        if (dirent.type == CPFS_ITYP_DIR) throw CpfsError(IsDirectory);
        Inode *inode = inode_get(dirent.ino);
        dir_remove_entry(dirpath, *parent, deoff, inode, path);
        return true;
    }
    bool call_chmod(
            char const *const path,
            CpfsPerms const perms) {
        Inode *const inode = path_inode(path);
        // clobber the perm bits
        inode->perms = perms;
        inode->ctime = optime();
        assert(valid_inode(*inode));
        return true;
    }
    bool call_chown(
            char const *const path,
            CpfsUid const uid,
            CpfsGid const gid) {
        Inode *inode = path_inode(path);
        bool updctime = false;
        if (uid != (decltype(uid))-1) {
            if (inode->uid != uid)
                updctime = true;
            inode->uid = uid;
        }
        if (gid != (decltype(gid))-1) {
            if (inode->gid != gid)
                updctime = true;
            inode->gid = gid;
        }
        if (updctime) {
            inode->ctime = optime();
            if (inode->perms.perms & 0111)
                inode->perms.perms &= ~(CPFS_PERM_SUID|CPFS_PERM_SGID);
        }
        assert(valid_inode(*inode));
        return true;
    }
    bool call_rename(
            char const *const oldpath,
            char const *const newpath) {
        char olddirpath[CpfsPathMax] = {'\0'};
        char const *const oldname = path_split(oldpath, olddirpath);
        Inode *const olddirinode = path_inode(olddirpath);
        Dirent olddirent;
        Offset olddiroff;
        if (!dir_find(olddirpath, *olddirinode, oldname, olddirent, olddiroff)) {
            throw CpfsError(PathNotFound);
        }

        Inode *theinode = inode_get(olddirent.ino);

        char newdirpath[CpfsPathMax] = {'\0'};
        char const *const newname = path_split(newpath, newdirpath);
        Inode *const newdirinode = path_inode(newdirpath);

        // find an obstructing entry and remove it
        {
            struct Dirent obdirent = Dirent();
            Offset obdeoff = -1;

            assert(!cpfs_errno_isset());
            // check if the new path already exists and remove it
            if (dir_find(newdirpath, *newdirinode, newname, obdirent, obdeoff)) {
                Inode *obinode = inode_get(obdirent.ino);

                // see rename(3)
                if (inode_is_dir(*obinode)) {
                    if (!inode_is_dir(*theinode)) throw CpfsError(IsDirectory);
                    if (dir_size(*obinode)) throw CpfsError(DirectoryNotEmpty);
                } else {
                    if (inode_is_dir(*theinode)) throw CpfsError(NotDirectory);
                }
                dir_remove_entry(newdirpath, *newdirinode, obdeoff, obinode, newpath);
            }
            assert(!dir_has_name(newdirpath, *newdirinode, newname));
            assert(!cpfs_errno_isset());
            dir_add_entry(newdirpath, *newdirinode, newname, *theinode);
            dir_remove_entry(olddirpath, *olddirinode, olddiroff, theinode, oldpath);
        }
        return true;
    }

    bool call_symlink(
            char const *target,
            char const *path,
            CpfsUid uid,
            CpfsGid gid)
    {
        bool retval = false;

        struct Inode *inode = NULL;
        ssize_t count = -1;

        if (!(inode = create_inode(path, CPFS_ITYP_LNK, (CpfsPerms){perms: 00777}, uid, gid)))
            goto out;
        count = strlen(target);
        if (count != inode_write(inode, target, count, 0))
            goto out;

        retval = true;
    out:
        return retval;
    }

    bool call_readlink(
            char const *const path,
            char *const buf,
            size_t const len)
    {
        bool retval = false;

        struct Inode const *inode = NULL;
        ssize_t readret = -1;

        if (!(inode = path_inode_ro(path)))
            goto out;
        if (inode->type != CPFS_ITYP_LNK) {
            cpfs_errno_set(NotSymlink);
            goto out;
        }
        if (-1 == (readret = inode_read(inode, buf, len - 1, 0)))
            goto out;
        retval = true;
    out:
        return retval;
    }
    bool call_link(char const *oldpath, char const *newpath) {
        Inode *const inode = path_inode(oldpath);
        char newdirpath[CpfsPathMax] = {'\0'};
        char const *const newname = path_split(newpath, newdirpath);
        Inode *const newparent = path_inode(newdirpath);
        dir_add_entry(newdirpath, *newparent, newname, *inode);
        inode->ctime = optime();
        assert(valid_inode(*inode));
        return true;
    }
};

template <typename Retval, typename Op, typename... Args>
Retval single_op_wrapper(
        Retval const failval,
        char const *const oplog,
        char const *const parmlog,
        Op const op,
        Cpfs &cpfs,
        Args &...args) {
    CallContext callctx(cpfs);
    Retval retval(failval);
    try {
        retval = (callctx.*op)(args...);
        assert(retval != failval);
        callctx.commit(cpfs);
    } catch (CpfsError const &exc) {
        cpfs_errno_set(exc.fserrno);
        //LOGF(Info, "Failed with %s", cpfs_errno_str(exc.fserrno));
    }
    if (parmlog)
        LOGF(Info, "%s(%s) = %|| (%s)", oplog, parmlog, retval, cpfs_errno_str(cpfs_errno_get()));
    return retval;
}

boost::format &&sprintfmm(boost::format &&format) {
    return format;
}

template<typename Value, typename ...Args>
boost::format &&sprintfmm(
        boost::format &&format,
        Value const &value,
        Args const &&...args) {
    return sprintfmm(format % value, args...);
}

template<typename ...Args>
std::string sprintfmm(char const *fmt, Args const &...args) {
    return str(sprintfmm(boost::format(fmt), args...));
}

template<typename Retval, typename ...Args>
Retval &&log_call(
        Retval &&retval,
        char const *argfmt,
        char const *callname,
        Args ...args) {
    LOGF(Info, "%s(%s) = %||", callname, sprintfmm(argfmt, args...).c_str(), retval);
}

extern "C" {

Cpfs *cpfs_load(char const *path, CpfsOff size, CpfsOff off) {
    try {
        std::unique_ptr<Cpfs> cpfs(new Cpfs(path, size, off));
        return cpfs.release();
    } catch (std::exception const &exc) {
        LOGF(Error, "%s", exc.what());
    }
    return nullptr;
}

bool cpfs_unload(struct Cpfs *cpfs)
{
    LOG(Info, NULL);
    cpfs_errno_clear();
    delete cpfs;
    return !cpfs_errno_isset();
}

#define SINGLE_OP_WRAPPER(RETTYPE, FAILVAL, OP, PARMLOG, ...) \
    single_op_wrapper<RETTYPE>((FAILVAL), #OP, PARMLOG, &CallContext::call_##OP, ##__VA_ARGS__)


bool cpfs_statvfs(Cpfs *fsptr, CpfsStatvfs *stfs) {
    return SINGLE_OP_WRAPPER(bool, false, statvfs, "", *fsptr, stfs);
}
bool cpfs_stat(Cpfs *fsptr, char const *path, CpfsStat *const st) {
    return SINGLE_OP_WRAPPER(bool, false, stat, sprintfmm("\"%s\"", path).c_str(), *fsptr, path, st);
}
bool cpfs_fstat(Cpfs *fsptr, CpfsFd fd, CpfsStat *statbuf) {
    return SINGLE_OP_WRAPPER(bool, false, fstat, "", *fsptr, fd, statbuf);
}
CpfsFd cpfs_opendir(Cpfs *const fsptr, char const *const path) {
    return SINGLE_OP_WRAPPER(CpfsFd, -1, opendir, "", *fsptr, path);
}
CpfsFd cpfs_open(Cpfs *fsptr, char const *path) {
    return SINGLE_OP_WRAPPER(CpfsFd, -1, open, "", *fsptr, path);
}
bool cpfs_releasedir(Cpfs *const fsptr, CpfsFd const fd) {
    return SINGLE_OP_WRAPPER(bool, false, releasedir, "", *fsptr, fd);
}
bool cpfs_close(Cpfs *const fsptr, CpfsFd const fd) {
    return SINGLE_OP_WRAPPER(bool, false, close, "", *fsptr, fd);
}
bool cpfs_readdir(
        Cpfs *const fsptr,
        CpfsFd const fd,
        CpfsOff *const off,
        char *const name,
        CpfsStat *const st,
        bool const fullstat) {
    string const parmlog(sprintfmm("fd=%||, off=%||", fd, *off));
    auto const retval(SINGLE_OP_WRAPPER(bool, false, readdir, nullptr, *fsptr, fd, *off, name, *st, fullstat));
    LOGF(Info, "%s(%s) = %|| [%d] (name=\"%s\", off=%||)", "readdir", parmlog.c_str(), retval, cpfs_errno_str(cpfs_errno_get()), name, *off);
    return retval;
}
bool cpfs_mknod(
        Cpfs *const fsptr,
        char const *const path,
        CpfsInodeType const type,
        CpfsPerms const perms,
        CpfsUid const uid,
        CpfsGid const gid) {
    return SINGLE_OP_WRAPPER(bool, false, mknod, "", *fsptr, path, type, perms, uid, gid);
}
CpfsFd cpfs_create(
        Cpfs *const fsptr,
        char const *const path,
        CpfsInodeType const type,
        CpfsPerms const perms,
        CpfsUid const uid,
        CpfsGid const gid) {
    return SINGLE_OP_WRAPPER(CpfsFd, -1, create, "", *fsptr, path, type, perms, uid, gid);
}
bool cpfs_utimens(
        Cpfs *const fsptr,
        char const *const path,
        CpfsTime const tv[2]) {
    return SINGLE_OP_WRAPPER(bool, false, utimens, "", *fsptr, path, tv);
}
CpfsSizeRet cpfs_read(
        Cpfs *const fsptr,
        int const fd,
        void *const buf,
        size_t const count,
        CpfsOff const off) {
    return SINGLE_OP_WRAPPER(CpfsSizeRet, -1, read, "", *fsptr, fd, buf, count, off);
}
CpfsSizeRet cpfs_write(
        struct Cpfs *fsptr,
        int const fd,
        void const *const buf,
        size_t const count,
        CpfsOff const off) {
    return SINGLE_OP_WRAPPER(CpfsSizeRet, -1, write, "", *fsptr, fd, buf, count, off);
}
bool cpfs_fnop(
        Cpfs *const fsptr,
        CpfsFd const fd) {
    return SINGLE_OP_WRAPPER(bool, false, fnop, "", *fsptr, fd);
}
bool cpfs_truncate(
        struct Cpfs *fsptr,
        char const *path,
        CpfsOff len) {
    return SINGLE_OP_WRAPPER(bool, false, truncate, "", *fsptr, path, len);
}
bool cpfs_ftruncate(
        struct Cpfs *fsptr,
        int const fd,
        CpfsOff const len) {
    return SINGLE_OP_WRAPPER(bool, false, ftruncate, "", *fsptr, fd, len);
}
bool cpfs_rmdir(
        struct Cpfs *fsptr,
        char const *const path) {
    return SINGLE_OP_WRAPPER(bool, false, rmdir, sprintfmm("\"%s\"", path).c_str(), *fsptr, path);
}
bool cpfs_unlink(Cpfs *const fsptr, char const *const path) {
    return SINGLE_OP_WRAPPER(bool, false, unlink, sprintfmm("\"%s\"", path).c_str(), *fsptr, path);
}
bool cpfs_chmod(
        struct Cpfs *fsptr,
        char const *path,
        CpfsPerms const perms) {
    return SINGLE_OP_WRAPPER(bool, false, chmod, "", *fsptr, path, perms);
}
bool cpfs_chown(
        struct Cpfs *fsptr,
        char const *const path,
        CpfsUid const uid,
        CpfsGid const gid) {
    return SINGLE_OP_WRAPPER(bool, false, chown, "", *fsptr, path, uid, gid);
}
bool cpfs_rename(
        struct Cpfs *fsptr,
        char const *const oldpath,
        char const *const newpath) {
    return SINGLE_OP_WRAPPER(bool, false, rename, "", *fsptr, oldpath, newpath);
}
bool cpfs_symlink(
        struct Cpfs *fsptr,
        char const *target,
        char const *path,
        CpfsUid uid,
        CpfsGid gid) {
    return SINGLE_OP_WRAPPER(bool, false, symlink, "", *fsptr, target, path, uid, gid);
}
bool cpfs_readlink(
        struct Cpfs *fsptr,
        char const *const path,
        char *const buf,
        size_t const len) {
    return SINGLE_OP_WRAPPER(bool, false, readlink, "", *fsptr, path, buf, len);
}
bool cpfs_link(
        struct Cpfs *fsptr,
        char const *oldpath,
        char const *newpath) {
    return SINGLE_OP_WRAPPER(bool, false, link, "", *fsptr, oldpath, newpath);
}
struct CpfsParams const *cpfs_params(Cpfs *const cpfs) {
    return &cpfs->params;
}
CpfsTime timespec_to_cpfstime(timespec const *const ts) {
    return ts->tv_sec * 1000000 + (ts->tv_nsec / 1000);
}
struct timespec cpfstime_to_timespec(CpfsTime const ct) {
    struct timespec ts = {};
    ts.tv_sec = ct / 1000000;
    ts.tv_nsec = 1000 * (ct % 1000000);
    return ts;
}

} // extern "C"

static void bootrec_reset(
        Device &device,
        size_t blksize,
        Bootrec &bootrec) {
    if (blksize == -1) blksize = 512;
    memset(&bootrec, 0, sizeof(bootrec));
    strncpy(bootrec.fsident, "cpfs1", sizeof(bootrec.fsident));
    bootrec.blksize = blksize;
    CpfsOff const endoff = device.size();
    LOGF(Info, boost::format("Device size is %|| bytes") % endoff);
    bootrec.blkcount = endoff / bootrec.blksize;
    // br, bm, root inode
    assert(bootrec.blkcount >= 3);
    time_t timeret = -1;
    bootrec.serial = static_cast<decltype(bootrec.serial)>(time(&timeret));
    assert(timeret != -1);
    device.write(&bootrec, sizeof(bootrec), 0);
}
static bool bitmap_reset(Geo const &geo, Device &device) {
    LOGF(Info, "Resetting bitmap");
    size_t const blksize(geo.block_size);
    char unsigned *const blkbuf = VOID_CAST(char unsigned *, alloca(blksize));
    /* zeroing all but the last bitmap block */
    memset(blkbuf, 0, geo.block_size);
    for (   Blkno blkno = geo.bitmap_start;
            blkno < geo.bitmap_end - 1;
            ++blkno) {
        device.write_block(blkno, blkbuf, blksize);
    }
    assert(util_mem_is_zeroed(blkbuf, geo.block_size));

    /* mark allocated the bits in the final bitmap block that overhang the end of data region */

    Blkno const overhang_bit_offset =
        geo.data_length - (geo.bitmap_length - 1) * geo.bitmap_density;
    size_t byte_index = NUMERIC_CAST(decltype(byte_index), overhang_bit_offset / CHAR_BIT);
    LOGF(Info, "Bitmap overhangs by %"PRIdBLKNO" blocks.", overhang_bit_offset);
    // could the overhang not exist? then the second condition should be <=
    assert(0 < overhang_bit_offset && overhang_bit_offset <= geo.bitmap_density);
    blkbuf[byte_index] = ~((1 << (overhang_bit_offset % CHAR_BIT)) - 1);
    while (++byte_index < geo.block_size)
        blkbuf[byte_index] = -1;
    device.write_block(geo.bitmap_end - 1, blkbuf, blksize);
    LOGF(Info, "Reset %"PRIdBLKNO" bitmap blocks.", geo.bitmap_length);
    return true;
}
LINKAGE("C") bool cpfs_mkfs(
        char const *const path,
        CpfsOff const size,
        CpfsOff const off,
        ssize_t const blksize) {
    try {
        Device device(path, size, off);
        Bootrec bootrec;
        bootrec_reset(device, blksize, bootrec);
        Geo geo;
        cpfs_load_geometry(&bootrec, &geo);
        if (!bitmap_reset(geo, device)) return false;
        device.flush();
        if (!CallContext::root_reset(path, size, off)) return false;
        return true;
    } catch (std::exception const &exc) {
        LOGF(Error, "%s", exc.what());
        return false;
    }
    return false;
}

} // namespace cpfs {
